CS 505: Computer Structures, Fall 2003
Second Examination

1. (10 points) Recall that there are two kinds of CMOS transistors:
   • PMOS transistors, triggered when a 0 is applied to the "gate" terminal, and able to pass 1's easily.
   • NMOS transistors, triggered when a 1 is applied to the "gate" terminal, and able to pass 0's easily.
   Draw an inverter circuit using CMOS transistors. Clearly label the input and output of the circuit, as well as any other wires supplying values to the circuit. Recall that an inverter computes the NOT function.
2. Recall the "theee C's" of categorizing cache misses.
   1. (6 points) Which one is reduced by using set associativity?
   2. (6 points) Which one is not found in fully associative caches?
   3. (6 points) Which one cannot be avoided in general?
   4. (6 points) List two changes to a cache design that would each reduce misses caused by the kind of miss that is not an answer to the first three questions.
3. Consider the following x86 assembly language code segment, with line numbers added for reference:

   01         movl    $0, %eax
   02         movl    $0, %ebx
   03 loop:
   04         movl    %eax, %ecx
   05         andl    $1, %ecx
   06         cmpl    $1, %ecx
   07         je      over
   08         incl    %ebx
   09 over:
   10         incl    %eax
   11         cmpl    $9999, %eax
   12         jle     loop
   

   1. (7 points) What will be the value of the %eax register when the loop described by this code segment is finished?
   2. For each of the following branch predictors, what will be the misprediction rate for the branch on line 7? Your answer should be accurate to within 1% of the correct answer.
      1. (7 points) A Smith predictor with 128 1-bit entries
      2. (7 points) A Smith predictor with 128 2-bit entries
      3. (7 points) A two-level adaptive branch predictor with a history length of 7 and 128 2-bit entries.
4. (10 points) Consider two systems:
   • System A: a single 2.0 GHz Pentium 4 workstation with 1024MB of RAM.
   • System B: a network of 16 2.0 GHz Pentium 4 workstations, each with 64MB of RAM. Special software is used to allow the workstations to function as a message-passing parallel computer.
   Describe how it is possible that a program on System B could run more than 16 times as fast as a program on System A.
5. Out-of-order execution is a solution to the problem of static scheduling in the presence of instructions whose latencies cannot be predicted at compile-time. Consider the following four systems that do execution in order:
   • System A has an 8KB L1 data cache with a 1-cycle access time and an average miss rate of 10%, a 256KB L2 data cache with a 5 cycle access time and an average miss rate of 0.5%, and a 500 cycle access time to main memory.
   • System B has only an 8KB data cache with a 1-cycle access time and an average miss rate of 10%, and a 500 cycle access time to main memory.
   • System C has no data cache and a 500 cycle access time to main memory
   • System D has no data cache and a 1-cycle access time to main memory.
   We are considering adding dynamic scheduling to each of these systems.
   1. (8 points) Which of these systems is likely to benefit the most, in terms of speedup over the inorder system, from the addition of dynamic scheduling? Why?
   2. (8 points) Which system is likely to benefit the least? Why?
   Hint: For each question there is exactly one right answer. The answers to the two questions are not the same and are not a trick (e.g. "none of the above"). You don't need any more information to answer this question.
6. The following questions deal with virtual memory:
   1. (4 points) Suppose we have a system with so much physical memory that we will never run out of memory. Is it still a good idea to use virtual memory on this system? Why or why not?
   2. (6 points) List two reasons why virtually addressed caches usually need to have more tag bits than physically addressed caches.
7. On one particular set of benchmarks for an SMT system, the branch misprediction rate goes from 5% to 9.1% when the number of threads is increased from 1 to 8.
   1. (6 points) Why does the branch misprediction rate increase?
   2. (6 points) Is it possible that the 8-thread scenario will have a speedup over the 1-thread scenario even with the higher branch misprediction rate? Why or why not?